Quasi-Monte Carlo method

In numerical analysis, a quasi-Monte Carlo method is a method for the computation of an integral (or some other problem) that is based on low-discrepancy sequences. This is in contrast to a regular Monte Carlo method, which is based on sequences of pseudorandom numbers.

Monte Carlo and quasi-Monte Carlo methods are stated in a similar way. The problem is to approximate the integral of a function f as the average of the function evaluated at a set of points x₁, ..., x_N.

where Ī^s is the s-dimensional unit cube, Ī^s = [0, 1] × ... × [0, 1]. (Thus each x_i is a vector of s elements.) In a Monte Carlo method, the set x₁, ..., x_N is a subsequence of pseudorandom numbers. In a quasi-Monte Carlo method, the set is a subsequence of a low-discrepancy sequence.

The approximation error of a method of the above type is bounded by a term proportional to the discrepancy of the set x₁, ..., x_N, by the Koksma-Hlawka inequality. The discrepancy of sequences typically used for the quasi-Monte Carlo method is bounded by a constant times

In comparison, with probability one, the expected discrepancy of a uniform random sequence (as used in the Monte Carlo method) has an order of convergence

by the law of the iterated logarithm.

Thus it would appear that the accuracy of the quasi-Monte Carlo method increases faster than that of the Monte Carlo method. However, Morokoff and Caflisch cite examples of problems in which the advantage of the quasi-Monte Carlo is less than expected theoretically. Still, in the examples studied by Morokoff and Caflisch, the quasi-Monte Carlo method did yield a more accurate result than the Monte Carlo method with the same number of points.

Morokoff and Caflisch remark that the advantage of the quasi-Monte Carlo method is greater if the integrand is smooth, and the number of dimensions s of the integral is small. A technique, coined randomized quasi-Monte Carlo, that mixes quasi-Monte Carlo with traditional Monte Carlo, extends the benefits of quasi-Monte Carlo to medium to large s.

Contents 1 Application areas 2 See also 3 References 4 External links

Application areas

• Monte Carlo methods in finance

See also

• Monte Carlo method

References

• R. E. Caflisch, Monte Carlo and quasi-Monte Carlo methods, Acta Numerica vol. 7, Cambridge University Press, 1998, pp. 1-49.
• Josef Dick and Friedrich Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, Cambridge, 2010, ISBN 978-0-521-19159-3
• Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math., 1651, Springer, Berlin, 1997, ISBN 3-540-62606-9
• William J. Morokoff and Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), no. 6, 1251--1279 (At CiteSeer:[1])
• William J. Morokoff and Russel E. Caflisch, Quasi-Monte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218--230. (At CiteSeer: [2])
• Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-295-5
• Harald G. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957--1041
• Oto Strauch and Štefan Porubský, Distribution of Sequences: A Sampler, Peter Lang Publishing House, Frankfurt am Main 2005, ISBN 3-631-54013-2

External links

• A very intuitive and comprehensive introduction to Quasi-Monte Carlo methods